package com.lx.algorithm.heap;

import java.util.List;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-10 10:07:42
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-10     张李鑫                     1.0         1.0 Version
 */
public class Problem {
    /**
     * 最大线段重合问题（用堆的实现）
     *
     * 给定很多线段，每个线段都有两个数[start, end]，
     * 表示线段开始位置和结束位置，左右都是闭区间
     * 规定：
     * 1）线段的开始和结束位置一定都是整数值
     * 2）线段重合区域的长度必须>=1
     * 返回线段最多重合区域中，包含了几条线段
     * radix
     */


    /**
     * 给定一个整型数组，int[] arr；和一个布尔类型数组，boolean[] op
     * 两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作
     * arr = [ 3   ,   3   ,   1   ,  2,      1,      2,      5…
     * op = [ T   ,   T,      T,     T,      F,      T,       F…
     * 依次表示：3用户购买了一件商品，3用户购买了一件商品，1用户购买了一件商品，2用户购买了一件商品，1用户退货了一件商品，2用户购买了一件商品，5用户退货了一件商品…
     * <p>
     * 一对arr[i]和op[i]就代表一个事件：
     * 用户号为arr[i]，op[i] == T就代表这个用户购买了一件商品
     * op[i] == F就代表这个用户退货了一件商品
     * 现在你作为电商平台负责人，你想在每一个事件到来的时候，
     * 都给购买次数最多的前K名用户颁奖。
     * 所以每个事件发生后，你都需要一个得奖名单（得奖区）。
     * <p>
     * 1，如果某个用户购买商品数为0，但是又发生了退货事件，
     * 则认为该事件无效，得奖名单和上一个事件发生后一致，例子中的5用户
     * 2，某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
     * 3，每次都是最多K个用户得奖，K也为传入的参数
     * 如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果
     * <p>
     * 得奖系统的规则：
     * 4，得奖系统分为得奖区和候选区，任何用户只要购买数>0，
     * 一定在这两个区域中的一个
     * 5，购买数最大的前K名用户进入得奖区，
     * 在最初时如果得奖区没有到达K个用户，那么新来的用户直接进入得奖区
     * 6，如果购买数不足以进入得奖区的用户，进入候选区
     * <p>
     * 得奖系统的规则：
     * 7，如果候选区购买数最多的用户，已经足以进入得奖区，
     * 该用户就会替换得奖区中购买数最少的用户（大于才能替换），
     * 如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户
     * 如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户
     * <p>
     * 得奖系统的规则：
     * 8，候选区和得奖区是两套时间，
     * 因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有
     * 从得奖区出来进入候选区的用户，得奖区时间删除，
     * 进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
     * 从候选区出来进入得奖区的用户，候选区时间删除，
     * 进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
     */
}
